home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 126-150 / disk_147 / sys / atari / atari.zoo / alloc.c next >
C/C++ Source or Header  |  1988-07-25  |  5KB  |  199 lines
  1. /* alloc.c -- replacement malloc and friends
  2.  *
  3.  * author :  Sandra Loosemore
  4.  * date   :  24 Oct 1987
  5.  *
  6.  * This file is a replacement for the usual definitions of malloc and free.
  7.  * The ST Malloc routine is called to get more memory from the system.
  8.  * Note that the memory that is Malloc'ed is never Mfree'd.
  9.  *
  10.  */
  11.  
  12.  
  13. #include <osbind.h>
  14. #define NULL 0L
  15.  
  16.  
  17. /* This is the default size for grabbing memory from the system with Malloc.
  18.  *    If you try to malloc a piece bigger than this, it will Malloc a
  19.  *    piece exactly the right size.  Ideally, it should be quite a bit
  20.  *    larger than the average size of things you are allocating (assuming
  21.  *    you are going to allocate lots of them).
  22.  */
  23.  
  24. static long mchunk = 16384L;           /* Size for grabbing memory */
  25.  
  26.  
  27. /* Each call to malloc returns a chunk; freeing it puts the chunk on
  28.  *    the free list.  The "next" field is only used for freed blocks.
  29.  *      The "nbytes" field is the size of the body of the chunk, not
  30.  *    the entire chunk.
  31.  */
  32.  
  33. typedef struct chunk {
  34.     long nbytes;
  35.     union {
  36.         struct chunk *next;
  37.         char body[1];
  38.         } info;
  39.     } CHUNK;
  40.  
  41. #define Nbytes(c) (c)->nbytes
  42. #define Next(c) (c)->info.next
  43. #define Body(c) (c)->info.body
  44.  
  45. static CHUNK *freelist = NULL;
  46.  
  47.  
  48. /* Return a block at least "size" bytes long.  Grab more memory if there
  49.  *     isn't anything on the free list that big.  If the block is just big
  50.  *     enough, remove it from the free list and return the whole thing.
  51.  *    Otherwise, carve a piece off the front.
  52.  * Note that the size is rounded up to make it an even number, and it must
  53.  *    also be at least big enough to hold the next pointer when the block
  54.  *    is freed.
  55.  */
  56.  
  57. char *alloc (size)
  58.     long size;
  59. {   register CHUNK *this, *last, *new;
  60.     long temp;
  61.     size = (size + 1) & 0xfffe;                       /* Word alignment */
  62.     if (size < sizeof(CHUNK *))  size = sizeof(CHUNK *);   /* Minimum size */
  63.     this = freelist;
  64.     last = NULL;
  65.     while (this != NULL)  {
  66.         if (Nbytes(this) >= size)  break;
  67.         last = this;
  68.         this = Next(this);
  69.         }
  70.     if (this == NULL)  {
  71.         temp = ((size < mchunk) ? mchunk : size);
  72.         this = (CHUNK *) Malloc (temp + sizeof(long));
  73.         if (!this)  return(NULL);
  74.         Nbytes(this) = temp;
  75.     free(Body(this));
  76.         this = freelist;
  77.     last = NULL;
  78.     while (this != NULL)  {
  79.             if (Nbytes(this) >= size)  break;
  80.             last = this;
  81.             this = Next(this);
  82.         }
  83.         }
  84.     temp = Nbytes(this) - size - sizeof(long);
  85.     if (temp <= sizeof(CHUNK))  {               /* Use the whole thing */
  86.         if (last)
  87.         Next(last) = Next(this);
  88.     else
  89.         freelist = Next(this);
  90.         return(Body(this));
  91.         }
  92.     else  {                                         /* Grab some off end */
  93.         new = (CHUNK *) ((char *)this + size + sizeof(long));
  94.     Nbytes(new) = temp;
  95.     Next(new) = Next(this);
  96.     if (last)
  97.         Next(last) = new;
  98.     else
  99.         freelist = new;
  100.     Nbytes(this) = size;
  101.     return(Body(this));
  102.         }
  103.     }
  104.  
  105.  
  106.  
  107. /* These are the user-accessible entry points */
  108.  
  109. char *malloc (size)
  110.     unsigned size;
  111. {   return (alloc((long)size));
  112.     }
  113.  
  114. #if 0    /* calloc not used in mg */
  115. char *calloc (number, size)
  116.     unsigned number, size;
  117. {   return (alloc ((long)number*size));
  118.     }
  119. #endif
  120.  
  121. char *realloc (oldptr, newsize)
  122.     register char *oldptr;
  123.     unsigned newsize;
  124. {   long oldsize;
  125.     register char *newptr;
  126.     register unsigned i;
  127.     CHUNK *block;
  128.     block = (CHUNK *) (oldptr - sizeof(long));
  129.     oldsize = Nbytes(block);
  130.     if (newsize > oldsize)  {
  131.         newptr = alloc((long)newsize);
  132.         for (i=0; i<oldsize; i++)
  133.         newptr[i] = oldptr[i];
  134.         free(oldptr);        
  135.     return(newptr);
  136.         }
  137.     else
  138.         return(oldptr);
  139.     }
  140.  
  141.     
  142. /* Free a pointer.  The freelist is maintained in sorted order, so loop
  143.  *    through until we find the block on either side of the one we're
  144.  *    freeing.  Then see if we can merge this block with either one.
  145.  */
  146.  
  147. free (ptr)
  148.     char *ptr;
  149. {   register CHUNK *last, *this, *block;
  150.  
  151.     /* Find where to insert the block in the free list. */
  152.  
  153.     block = (CHUNK *)(ptr - sizeof(long));
  154.     this = freelist;
  155.     last = NULL;
  156.     while (this && (this < block))  {
  157.         last = this;
  158.     this = Next(this);
  159.     }
  160.  
  161.     /* Can we merge it with the next block?  */
  162.  
  163.     if (this && ((ptr + Nbytes(block)) == this))  {
  164.         Nbytes(block) = Nbytes(block) + Nbytes(this) + sizeof(long);
  165.     Next(block) = Next(this);
  166.     }
  167.     else
  168.         Next(block) = this;
  169.  
  170.     /* Can we merge it with the previous block?  */
  171.  
  172.     if (last && ((Body(last) + Nbytes(last)) == block))  {
  173.         Nbytes(last) = Nbytes(last) + Nbytes(block) + sizeof(long);
  174.     Next(last) = Next(block);
  175.         }
  176.     else if (last)
  177.         Next(last) = block;
  178.     else
  179.         freelist = block;
  180.     }
  181.  
  182.  
  183. /* A debug routine to help me make sure that the freelist is compacted
  184.  *    properly.
  185.  */
  186.  
  187. #ifdef DEBUG
  188.  
  189. dumpfree ()
  190. {   CHUNK *junk;
  191.     printf ("Dump of free list:\n");
  192.     junk = freelist;
  193.     while (junk)  {
  194.         printf ("    Base %ld, size %ld\n", (long)(Body(junk)), Nbytes(junk));
  195.     junk = Next(junk);
  196.     }
  197.     }
  198. #endif
  199.